package leetcode

import kotlinetc.println

/**
Given an sort.getArray of non-negative integers, you are initially positioned at the first index of the sort.getArray.

Each element in the sort.getArray represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
Jump 1 step from index 0 to 1, then 3 steps to the last index.
 */
fun main(args: Array<String>) {


    //[10,9,8,7,6,5,4,3,2,1,1,0]
    jump(intArrayOf(10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 0)).println()
}

/**
 * [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 0]
 * 从初始位置出发，为了能够走最小步数，那么就必须保证每一步都能走的足够远
 * 所以在10位置的时候 先判断10步之内是否可以到达终点，因为不可以，那么就寻求走最远
 * 由于10位置可以走10的距离，在此距离内9 可以走1+9步 最远可以达到 index 11的位置(从10走到9需要一步)
 * 所以下一步
 */
fun jump(nums: IntArray): Int {

    val finalPos = nums.size - 1
    var currPos = 0
    var step = 0
    var max: Int
    var k: Int

    while (currPos != finalPos) {
        val maxStepSize = nums[currPos]

        val end = maxStepSize + currPos
        if (end >= finalPos) {
            step++
            break
        } else {
            //寻找距离+步长最大的值
            k = currPos + 1
            max = 0
            while (k <= end) {
                if (nums[k] + k > max) {
                    currPos = k
                    max = nums[k] + k
                }
                k++
            }
            step++
        }

    }
    return step
}